package com.lw.leetcode.greedy.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 2033. 获取单值网格的最小操作数
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/5 15:51
 */
public class MinOperations2033 {

    public int minOperations(int[][] grid, int x) {
        int m = grid.length;
        int n = grid[0].length;
        int length = m * n;
        int[] arr = new int[length];
        int index = 0;
        int t = grid[0][0];
        for (int[] ints : grid) {
            for (int j = 0; j < n; j++) {
                int k = ints[j] - t;
                if (k % x != 0) {
                    return -1;
                }
                k /= x;
                arr[index++] = k;
            }
        }
        Arrays.sort(arr);
        t = -arr[0];
        int r = 0;
        for (int i = 0; i < length; i++) {
            arr[i] += t;
            r += arr[i];
        }
        int min = r;
        int l = 0;
        for (int i = 1; i < length; i++) {
            int c = arr[i] - arr[i - 1];
            l = l + c * i;
            r = r - (length - i) * c;
            min = Math.min(min, l + r);
        }
        return min;
    }

}
